Distance

Memory limit: 128 MB

We consider the distance between positive integers in this problem, defined as follows. A single operation consists in either multiplying a given number by a prime number¹ or dividing it by a prime number (if it does divide without a remainder). The distance between the numbers and , denoted , is the minimum number of operations it takes to transform the number into the number . For example, .

Observe that the function is indeed a distance function - for any positive integers , and the following hold:

• the distance between a number and itself is 0: ,
• the distance from to is the same as from to : , and
• the triangle inequality holds: .

Input

In the first line of standard input there is a single integer (). In the following lines the numbers () are given, one per line.

In tests worth 30% of total point it additionally holds that .

Output

Your program should print exactly lines to the standard output, a single integer in each line. The -th line should give the minimum such that: , and is minimal.

Example

For the input data:

6
1
2
3
4
5
6

the correct result is:

2
1
1
2
1
2

Task author: Wojciech Smietanka.

1. Recall that a positive integer is prime if and only of it has exactly two distinct divisors: one and itself.